﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace CodeTop.复习八月份
{
    public class Solution105
    {
        public TreeNode BuildTree(int[] preorder, int[] inorder)
        {


            return DFS(preorder, 0, preorder.Length - 1, inorder, 0, inorder.Length - 1);


        }

        private TreeNode DFS(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd)
        {

            if (pStart > pEnd)
            {
                return null;
            }


            TreeNode root=new TreeNode();
            int mid = 0;
            for(int i = iStart; i <= iEnd; i++)
            {
                if (inorder[i] == preorder[pStart])
                {
                    mid = i;break;
                }


            }
            root.val = preorder[pStart];
            int leftLen = mid - iStart;
            int rightLen = iEnd - mid;

            root.left = DFS(preorder, pStart + 1, pStart + leftLen, inorder, iStart, mid - 1);
            root.right = DFS(preorder, pStart + leftLen+1, pEnd, inorder, mid + 1, iEnd);
            return root;



        }
    }


    class Program105
    {


        static void Main105(string[] args)
        {
            int[] preorder = [3, 9, 20, 15, 7];
            int[] inorder = [9, 3, 15, 20, 7];

            Solution105 solution = new Solution105();
            solution.BuildTree(preorder, inorder);

        }
    }
}
